ucore lab2
ucore lab1初步实现了一个可以读磁盘并且加载ELF执行文件格式的系统,也可以响应和显示字符。仅仅如此并不足以满足操作系统的要求,进程在执行过程中需要系统分配内存等资源。为了高效地管理内存,ucore lab2采用了段页式机制,把其中段式内存的功能弱化,实现以分页为主的内存管理。
与lab1相比,lab2有两方面的扩展,首先,bootloader
的工作有增加, 在bootloader
中,完成了对物理内存资源的探测工作,让ucore kernel
在后续执行中能够基于bootloader
探测出的物理内存情况进行物理内存管理初始 化工作。其次,bootloader
不像lab1那样,直接调用kern_init
函数,而是先调用位于/kern/init/entry.S
中的kern_entry
函数。kern_entry
函数的主要任务是为执行kern_init
建立 一个良好的C语言运行环境(设置堆栈),而且临时建立了一个段映射关系,为之后建立分页机制的过程做一个准备。
kern_init
函数在完成一些输出并对lab1实验结果的检查后,将进入物理内存管理初始化的工作,即调用pmm_init
函数完成物理内存的管理,这也是我们lab2的内容。接着是执行中断和异常相关的初始化工作,即调用pic_init
函数和idt_init
函数等,这些工作与lab1的中断异常初始化工作的内容是相同的。
探测系统物理内存布局
一般来说,获取内存大小的方法有BIOS中断调用和直接探测两种,但BIOS中断调用方法只能在实模式下完成,而直接探测必须在保护模式下完成。通过BIOS中断获取系统布局有三种方式,分别为88h,e801h,e820h,但是并非在所有情况中这三种模式都可以工作。在lab中,我们通过e820h中断来获取内存信息。BIOS中断必须在实模式下工作,故我们在bootloader
进入保护模式之前调用E820h中断,将映射结构保存在物理地址0x8000处。
BIOS通过系统内存映射地址描述符(Address Range Descriptor)格式来表示系统物理内存布局,其具体表示如下:
1 | struct e820map { |
物理内存的探测是在bootasm.S
中实现的:
1 | probe_memory: |
BIOS查找出各个部分的内存布局条目,放入到一个保存地址范围描述符结构的缓冲区中,以便于后续的ucore的物理内存管理。
以页为单位管理物理内存
1 | struct Page { |
其中各成员变量,ref表示这页被页表的引用计数,如果这个页被页表引用了,即在某页表中有一个页表项设置了一个虚拟页到这个Page管理的物理页的映射关系,就会把Page的ref加一;反之,若页表项取消,即映射关系解除,就会把Page的ref减一。flags表示此物理页的状态标记,在kern/mm/memlayout.h
中的定义中可以看到
1 | /* Flags describing the status of a page frame */ |
page_link
是便于把多个连续内存空闲块链接在一起的双向链表指针。仅这个连续内存空闲块地址最小的一页(即首页, Head Page)会使用到此成员变量。连续内存空闲块利用这个页的成员变量page_link来链接比它地址小或大的其他连续内存空闲块。
为了管理非连续空闲内存块,我们定义了一个free_area_t
数据结构,包含了一个list_entry
结构的双向链表指针和记录当前空闲页的个数的无符号整型变量nr_free
,其中的链表指针指向了空闲的物理页。
1 | typedef struct { |
接下来需要解决两个问题:
- 管理页级物理内存空间所需的Page结构的内存空间从哪里开始,占多大空间?
- 空闲内存空间的起始地址在哪里?
1 | static void page_init(void) { |
首先根据bootloader
给出的内存布局信息找出最大的物理内存地址maxpa
,所需要管理的物理页面数为
1 | npage = maxpa / PGSIZE |
所需要空间为
1 | sizeof(struct Page) * npage |
ucore的BSS结束处再进行取整即为Page结构开始的物理地址,而空闲地址空间在管理空间(Page结构)的区域之后。
一个Page结构体管理的那个4K大小的物理页的信息究竟应该怎么得到?
由于一个struct Page和一块4K大小的物理空间是一一对应的, 所以ucore中采用的方法是将struct Page按照他们所管辖的物理页面的地址大小进行连续储存, 所以可以使用page2pa宏通过对page结构的首地址进行移位操作获得对应地址, 详情可见mm/pmm.h
, 其中pages可以认为是存储所有struct Page的首地址。
1 | static inline ppn_t |
first-fit 连续物理内存分配算法
first_fit
分配算法需要维护一个查找有序(地址按从小到大排列)空闲块(以页为最小单位的连续地址空间)的数据结构,lab2使用了双向链表结构来对空闲块进行管理。
init_memmap
1 | static void default_init_memmap(struct Page *base, size_t n) { |
之前的程序每次插入是在free_list之后,低地址的Page结构应该被插入在高地址Page的前方,正好被颠倒过来,应改为插入到free_list之前。
alloc_pages
1 | static struct Page* default_alloc_pages(size_t n) { |
free_pages
1 | static void default_free_pages(struct Page *base, size_t n) { |
系统执行中地址映射的三个阶段
在lab2中tools/kernel.ld
文件在链接阶段生成了ucore OS
执行代码的虚拟地址。通过ld工具形成的ucore的起始虚拟地址从0xC0100000
开始。
1 | ENTRY(kern_entry) |
bootloader
把ucore放在了起始物理地址为0x100000
的物理内存空间。lab2在不同阶段有不同的虚 拟地址、线性地址以及物理地址之间的映射关系。
1.bootloader
阶段,即从bootloader
的start函数 (在boot/bootasm.S
中)到执行ucore kernel的kern_entry函数之前,开启保护模式,创建启动段表其虚拟地址、线性地址以及物理地址之间的映射关系与lab1的一样,即:
1 | stage 1: virt addr = linear addr = phy addr |
2.从kern_entry
函数开始,到pmm_init
函数被 执行之前,创建页目录表,开启分页模式。
在entry.S
中设置好页目录表和页表项,将0~4M的线性地址一一映射到 物理地址。
1 | __boot_pgdir: |
接下来就要使能分页机制了,这主要是通过几条汇编指令(在kern/init/entry.S
中)实现的,主要做了两件事:
- 通过
movl %eax, %cr3
指令把页目录表的起始地址存入CR3寄存器中 - 通过
movl %eax, %cr0
设置把cr0中的CR0_PG
标志位。
执行完这几条指令后,系统进入了分页模式,虚拟地址、线性地址以及物理地址之间 的临时映射关系为:
1 | stage 2 before: |
其实仅仅比第一个阶段增加了下面一行的0xC0000000
偏移的映射,并且作用范围缩小到了0-4M。此时的内核(EIP)还在0~4M的低虚拟地址区域运行,而在之后,这个区域的虚拟内存是要给用户程序使用的。为此,需要使用一个绝对跳转来使内核跳转到高虚拟地址(kern/init/entry.S
中):
1 | # update eip |
跳转完毕后,通过把boot_pgdir[0]
对应的第一个页目录表项(0~4MB)清零来取消了临时的页映射关系。
1 | # unmap va 0 ~ 4M, it's temporary mapping |
最终,离开这个阶段时,虚拟地址、线性地址以及物理地址之间的映射关系为:
1 | stage 2: virt addr = linear addr = phy addr + 0xC0000000 # 线性地址在0~4MB之内三者的映射关系 |
这一阶段的目的是更新映射关系的同时将运行中的内核(EIP)从低虚拟地址“迁移”到高虚拟地址。但是仅仅映射了0~4MB。对于段表而言,也缺少了运行ucore所需的用户态段描述符和TSS(段)描述符相应表项。
3.从pmm_init
函数被调用开始,完善段表和页表。pmm_init
完成页目录项的填充,更新了段映射机制,加载新的段表,形成了我们希望的虚拟地址、线性地址以及物理地址之间的映射关系:
1 | stage 3: virt addr = linear addr = phy addr + 0xC0000000 |
最终形成的ucore内核虚拟地址空间
1 | /* * |
自映射机制
ucore把页目录表和页表放在一个连续的4MB虚拟地址空间中,并设置页目录表自身的虚地址<–>物理地址映射关系。在已知页目录表起始虚地址的情况下,通过连续扫描这特定的4MB虚拟地址空间,就很容易访问每个页目录表项和页表项内容。
ucore是这样设计的,首先设置了一个常量(memlayout.h
):
VPT=0xFAC00000
, 这个地址的二进制表示为:
1 | 1111 1010 1100 0000 0000 0000 0000 0000 |
高10位为1111 1010 11
,即10进制的1003
,中间10位为0,低12位也为0。在pmm.c
中有两个全局初始化变量
1 | pte_t * const vpt = (pte_t *)VPT; |
并在pmm_init函数执行了如下语句:
1 | boot_pgdir[PDX(VPT)] = PADDR(boot_pgdir) | PTE_P | PTE_W; |
vpd为页目录表的起始虚地址,PDX(vpd)=1003,boot_pgdir[1003]处存储了boot_pgdir
的物理地址。因为页表机制为二级页表,所以再次以boot_pgdir
为页表查找,PTX(vpd)=1003,最后对应的物理地址恰好为boot_pgdir
的物理地址。
vpt为页目录表中第一个目录表项指向的页表的起始虚地址,PDX(vpd)=1003,在boot_pgdir
查找页表项,PTX(vpd)=0,物理地址由页目录表中第一个目录表给出。
映射虚拟内存地址空间范围在memlayout.h
给出,表示ucore只支持896MB的物理内存空间。
1 | #define KERNBASE 0xC0000000 |
最大内核虚地址为常量
1 | #define KERNTOP (KERNBASE + KMEMSIZE)=0xF8000000 |
所以最大内核虚地址KERNTOP的页目录项虚地址为
1 | vpd+0xF8000000/0x400000*4=0xFAFEB000+0x3E0*4=0xFAFEBF80 |
最大内核虚地址KERNTOP的页表项虚地址为:
1 | vpt+0xF8000000/0x1000*4=0xFAC00000+0xF8000*4=0xFAFE0000 |
寻找虚拟地址对应的页表项
通过设置页表和对应的页表项,可建立虚拟内存地址和物理内存地址的对应关系。其中的 get_pte
函数是设置页表项环节中的一个重要步骤。此函数找到一个虚地址对应的二级页表项 的内核虚地址,如果此二级页表项不存在,则分配一个包含此项的二级页表。本练习需要补全kern/mm/pmm.c
中的get_pte
函数,实现其功能。
1 | pte_t * get_pte(pde_t *pgdir, uintptr_t la, bool create) { |
页目录项和页表项组成部分
pde
的各个组成部分为:
1 | 31 ----------------- 10 11 -- 9 8 7 6 5 4 3 2 1 0 |
其中31-10位地址为必须,avai可以由软件自由修改,不受kernel或硬件的控制。 考虑到uCore的page大小统一,不存在更换情况,所以S位对uCore无用。
其他位可能的潜在用处如下:
- A, D, W:这些与高速缓存相关的位,记录该页是否被访问过、不允许高速缓存过或执行了写穿透策略。如果uCore需要与硬件的cache进行交互(即这些位并非由硬件设定),就需要用到这些位。
- U:决定了当前页的访问权限(内核or用户):uCore可以通过这些位进行用户态和内核态程序访问权限的控制。
- R:决定了当前页的是否可写属性:当uCore需要对某一页进行保护的时候,需要用到此位,用于权限控制。
- P:决定当前页是否存在:uCore需要根据这个标志确定页表是否存在,并是否建立新的相关页表。
pte
的各个组成部分为:
1 | 31 ----------------- 10 11 -- 9 8 7 6 5 4 3 2 1 0 |
许多位与pde相同,不同的位有:
- C:与上述的D位相同。
- G:控制
TLB
地址的更新策略。 - D:该页是否被写过。如果uCore需要对高速缓存实现更复杂的控制则可能用到该位。同时,在页换入或是换出的时候可能需要判断是否更新高速缓存。
如果ucore执行过程中访问内存,出现了页访问异常,请问硬件要做哪些事情?
在x86的MMU模块进行访存的时候需要进行多级页表查找,如果pde或是pte中标志的页不存在,则会产生Page Fault异常(14号),具体来说CPU会进行下面的操作:
- 保存现场,存储当前的寄存器到主存储器中;
- 设置相应的寄存器记录当前出错程序的地址信息;
- 切换特权级(例如从ring3切换到ring0)
- 根据异常号读取idt表,确定ISR的地址,判断是否有进入中断门的权限;
- 跳转到ISR起始地址开始执行。
如果当前已经处于页访问异常的处理例程中,又发生了页访问异常,这对CPU来说是不允许的,会产生double fault异常,这种情况往往说明操作系统编码出现问题。
释放某虚地址所在的页并取消对应二级页表项的映射
1 | static inline void page_remove_pte(pde_t *pgdir, uintptr_t la, pte_t *ptep) { |
数据结构Page的全局变量(其实是一个数组)的每一项与页表中的页目录项和页表项有无对应关系?如果有,其对应关系?
Page数组主要用于管理物理的连续内存,数组中每一个Page对应物理内存中的一个页。页目录存在物理内存的页中,其每一项指向的页表也存储在物理内存的页中,页表中每一项存储的是页的物理内存地址,通过这个地址能够找到与之对应的Page结构。但Page结构本身是存储在单独的内存区域的(具体来说存储在内核段以上的区域)。
在内核态代码连续的内存管理中(例如PDE(0e0) c0000000-f8000000 38000000 urw),页表中的连续页表项对应的Page结构体在内存中也是连续的。
如果希望虚拟地址与物理地址相等,则需要如何修改Lab2,完成此事?
在Lab2中,由于地址映射的建立分为多个阶段完成,所以针对不同的阶段需要修改不同的代码以使得虚拟地址和物理地址相等。此处以之前的ucore指导书为准,分为四个阶段
第一阶段 在Bootloader
阶段,线性地址与物理地址相等,无需修改;
第二阶段 从kern_entry
到enable_paging
函数,主要采用段机制进行地址映射,需要修改的地方为init/entry.S中的gdt表项,去除KERNBASE有关的定义。此外,还需要修改ucore的链接脚本,将ucore起始的虚拟地址由0xC0100000改为0x00100000。
第三阶段 从enable_paging
函数开始到gdt_init
函数,虽然启动了页机制但是未更新段映射,这个时候页机制和段机制对于0xC0000000的偏移是叠加的。由于上一阶段已经修改过段机制的代码,这里仅需要将boot_map_segment
函数调用的KERNBASE
参数改为0,并取消VPT的递归自映射。这种情况下也没有必要专门建立0-4M物理地址映射,因为即使偏移叠加物理地址和虚拟地址还是相等的(最后有更详细的解释)。
第四阶段 之后的阶段由于完全启用了页机制,且页机制的相关参数已经在上一步设置完毕,所以无需修改,虚拟地址自会与物理地址相等。
实际上,上述四个阶段也可以分为下面的步骤:启用段机制、启用页机制、更换段机制。整个过程中uCore都必须保证正确的地址映射关系。前期uCore主要使用段机制进行地址偏移、后期uCore则使用页机制进行地址偏移。一个tricky的地方就在于二者的切换:uCore首先建立好偏移的页表,然后将第0项的页表偏移取消,考虑到uCore的内核不会超过4MB,因此在启动页机制之后,内核处的偏移关系仍然是由段机制来维护的。这就保证了启用页表之后,接下来读取gdt表的操作的代码能够正常执行,完成gdt表的修改之后,页机制的映射立刻起作用。此时才可以删除pde索引为0的相关页目录项。这也就解释了为何需要先设立0-4M的页目录项再将其清除的原因。
一级页表可以不在内存当中吗?
不可以。若一级页表不在内存中,那么在page fault时访问异常处理代码,那么在访问处理page fault的代码时发现一级页表不在内存中,再次触发page fault,然后再找,再触发,…于是宕机
另一种解释:处理器根本没有机制允许操作系统设置第一级页表是否存在。给cr3设置多少,第一级页表基址就是哪里。
建立页表的时候项数最少可以是多少?
1个。
一条指令会出现多次的访存操作,如果多次出现页缺失异常怎么办?
在我们的实现当中,如果出现多个页缺失异常,会在执行完指令之后将所有的异常一起处理一遍。
twd2: (1) 执行一条指令最多会有3次访存,取指令,读内存,写回内存,可能涉及到6个页面,它们都有可能缺页。这时只需要正常处理即可:处理一个缺页,返回后又发生缺页,继续处理。
(2) 如果二级页表和实际页面都不在物理内存中,处理器查询一级页表时能够得知二级页表不在内存的情况。由于没有二级页表,处理器无法得知实际页面到底在不在物理内存中(不过我感觉应该也不在)。注意,此时触发的缺页异常,cr2为最终需要访问的线性地址,与二级页表的地址无关(二级页表有线性地址吗?)。在解决缺页过程中的page table walk时,内核会给各级页表分配物理内存(若不存在)并填入映射信息(ucore是get_pte)。
在启动页机制后,不可能进行的操作包括()
- 取消段机制,只保留页机制
- 取消页机制,只保留段机制
- 取消页机制,也取消段机制
- 保留页机制,也保留段机制
不可能取消段机制,只保留页机制
页面置换算法 quiz9