项目组成 相对与实验一,实验二主要增加和修改的文件如上表所示。主要改动如下:
boot/bootasm.S:增加了对计算机系统中物理内存布局的探测功能
kern/init/entry.S:根据临时段表重新暂时建立好新的段空间,为进行分页做好准备
kern/mm/default_pmm.[ch]:提供基本的基于链表方法的物理内存管理(分配单位为页,即4096字节)
kern/mm/pmm.[ch]:pmm.h定义物理内存管理类框架struct pmm_manager,基于此通用框架可以实现不同的物理内存管理策略和算法(default_pmm.[ch] 实现了一个基于此框架的简单物理内存管理策略),pmm.c包含了对此物理内存管理类框架的访问,以及与建立、修改、访问页表相关的各种函数实现
kern/sync/sync.h:为确保内存管理修改相关数据时不被中断打断,提供两个功能,一个是保存eflag寄存器中的中断屏蔽位信息并屏蔽中断的功能,另一个是根据保存的中断屏蔽位信息来使能中断的功能(可不用细看)
libs/list.h:定义了通用双向链表结构以及相关的查找、插入等基本操作,这是建立基于链表方法的物理内存管理(以及其他内核功能)的基础,其他有类似双向链表需求的内核功能模块可直接使用list.h中定义的函数
libs/atomic.h:定义了对一个变量进行读写的原子操作,确保相关操作不被中断打断(可不用细看)
tools/kernel.ld:ld形成执行文件的地址所用到的链接脚本,修改了ucore的起始入口和代码段的起始地址
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ➜ lab2 make qemu WARNING: Image format was not specified for 'bin/ucore.img' and probing guessed raw. Automatically detecting the format is dangerous for raw images, write operations on block 0 will be restricted. Specify the 'raw' format explicitly to remove the restrictions. (THU.CST) os is loading ... Special kernel symbols: entry 0xc0100036 (phys) etext 0xc0105d24 (phys) edata 0xc011b000 (phys) end 0xc011bf28 (phys) Kernel executable memory footprint: 112 KB memory management: default_pmm_manager e820map: memory: 0009f c00, [00000000 , 0009f bff], type = 1. memory: 00000400 , [0009f c00, 0009f fff], type = 2. memory: 00010000 , [000f 0000, 000f ffff], type = 2. memory: 07 ee0000, [00100000 , 07f dffff], type = 1. memory: 00020000 , [07f e0000, 07f fffff], type = 2. memory: 00040000 , [fffc0000, ffffffff], type = 2. kernel panic at kern/mm/default_pmm.c:277 : assertion failed: (p0 = alloc_page()) == p2 - 1 stack trackback:Welcome to the kernel debug monitor!!
物理内存管理 本次实验主要完成ucore内核对物理内存的管理工作
为了完成物理内存管理,这里首先需要 探测可用的物理内存资源 ,了解到物理内存位于什么地方,有多大之后,就以固定页面大小来划分整个物理内存空间,并准备以此为最小内存分配单位来管理整个物理内存,管理在内核运行过程中每页内存,设定其可用状态(free的,used的,还是reserved的)
接着 ucore kernel 就要建立页表, 启动分页机制,让CPU的MMU把预先建立好的页表中的页表项读入到TLB中,根据页表项描述的虚拟页(Page)与物理页帧(Page Frame)的对应关系完成CPU对内存的读、写和执行操作
探测系统物理内存布局 操作系统需要知道了解整个计算机系统中的物理内存如何分布的,哪些被可用,哪些不可用,其基本方法是通过 BIOS 中断调用来帮助完成的
Linux 有多种办法可以获取内存容量,如果一种方式失效,它就会尝试其他办法
在 Linux 2.6 内核中,是用 detect_memory 函数来获取内存容量的,其函数在本质上是通过调用 BIOS 中断 0x15 实现的,分别是 BIOS 中断 0x15 的3个子功能,子功能号要存放到寄存器 EAX AX 中,如下:
EAX=0xE820:遍历主机上全部内存
AX=0xE801:分别检测低 15MB 和 16MB ~ 4GB 的内存,最大支持 4GB
AH=0x88:最多检测出 64MB 内存,如果实际内存超过此容量也按照 64MB 返回
uCore物理页结构 结构体 Page:用于管理各个内存页:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 struct list_entry { struct list_entry *prev , *next ; }; typedef struct list_entry list_entry_t ;struct Page { int ref; uint32_t flags; unsigned int property; list_entry_t page_link; };
在lab2中,flags 可以设置的位只有reserved
位和Property
位
reserved
位表示:当前页是否被保留,一旦保留该页,则该页无法用于分配
Property
位表示:当前页是否已被分配(为1则表示已分配)
uCore虚拟页结构 每个页表项(PTE)都由一个32位整数来存储数据,其结构如下:
1 2 3 4 31-12 9-11 8 7 6 5 4 3 2 1 0 +-------------- +------- +----- +---- +--- +--- +----- +----- +--- +--- +--- + | Offset | Avail | MBZ | PS | D | A | PCD | PWT | U | W | P | +-------------- +------- +----- +---- +--- +--- +----- +----- +--- +--- +--- +
0 - P resent:表示当前PTE所指向的物理页面是否驻留在内存中
1 - W riteable:表示是否允许读写
2 - U ser:表示该页的访问所需要的特权级(即User(ring 3)是否允许访问)
3 - P ageWriteThough:表示是否使用write through缓存写策略
4 - P ageCacheDisable:表示是否 不对 该页进行缓存
5 - A ccess:表示该页是否已被访问过
6 - D irty:表示该页是否已被修改
7 - P ageSize:表示该页的大小
8 - M ustBeZero:该位必须保留为0
9-11 - A vailable:第9-11这三位并没有被内核或中断所使用,可保留给OS使用
12-31 - O ffset:目标地址的后20位
uCore物理页链表 结构体 free_area_t:用于定义两个关键的全局变量
1 2 3 4 5 typedef struct { list_entry_t free_list; unsigned int nr_free; } free_area_t ;
虽然 ucore 把这两个变量放入了结构体,但是它还是喜欢把它们当做全局变量来用
uCore物理页的插链&脱链:
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 static inline list_entry_t *list_next (list_entry_t *listelm) { return listelm->next; } static inline void list_add(list_entry_t *listelm, list_entry_t *elm) { list_add_after(listelm, elm); } static inline void list_add_after(list_entry_t *listelm, list_entry_t *elm) { __list_add(elm, listelm, listelm->next); } static inline void list_add_before(list_entry_t *listelm, list_entry_t *elm) { __list_add(elm, listelm->prev, listelm); } static inline void __list_add(list_entry_t *elm, list_entry_t *prev, list_entry_t *next) { prev->next = next->prev = elm; elm->next = next; elm->prev = prev; } static inline void list_del(list_entry_t *listelm) { __list_del(listelm->prev, listelm->next); } static inline void __list_del(list_entry_t *prev, list_entry_t *next) { prev->next = next; next->prev = prev; }
uCore内存管理类 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 struct pmm_manager { const char *name; void (*init)(void ); void (*init_memmap)(struct Page *base, size_t n); struct Page *(*alloc_pages )(size_t n ); void (*free_pages)(struct Page *base, size_t n); size_t (*nr_free_pages)(void ); void (*check)(void ); }; #define PDXSHIFT 22 #define PDX(la) ((((uintptr_t)(la)) >> PDXSHIFT) & 0x3FF) #define PTXSHIFT 12 #define PTX(la) ((((uintptr_t)(la)) >> PTXSHIFT) & 0x3FF)
还有一些关于内存管理的宏定义:
PDX(la):可以用来获取 Directory,对应页目录项的索引
PTX(la):可以用来获取 Table,对应表项(物理页)的索引
KADDR(pa):返回物理地址pa对应的虚拟地址
set_page_ref(page,1):设置此页被引用一次
page2pa(page):得到page管理的那一页的物理地址
struct Page * alloc_page():分配一页出来
memset(void * s, char c, size_t n):设置s指向地址的前面n个字节为‘c’
PTE_P 0x001 :表示物理内存页存在
PTE_W 0x002 :表示物理内存页内容可写
PTE_U 0x004 :表示可以读取对应地址的物理内存页内容
练习0-把 lab1 的内容复制粘贴到 lab2 练习1-实现 first-fit 连续物理内存分配算法 分析 ucore 自带的代码:
default_init_memmap: 根据每个物理页帧(一个地址连续的 4K 字节大小单元内存)的情况来建立空闲页链表,且空闲页块应该是根据地址高低形成一个有序链表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #define PageReserved(page) test_bit(PG_reserved, &((page)->flags)) static void default_init_memmap (struct Page *base, size_t n) { assert(n > 0 ); struct Page *p = base; for (; p != base + n; p ++) { assert(PageReserved(p)); p->flags = p->property = 0 ; set_page_ref(p, 0 ); } base->property = n; SetPageProperty(base); nr_free += n; list_add(&free_list, &(base->page_link)); }
基于 base 来确定空闲页基地址,根据 n 来获取所需空闲页的数目
只有 base page 的 property 才会起作用,其他 page 的 property 置为0
进行一系列初始化,最后执行 list_add 添加入空闲页链表
default_alloc_pages: 分配指定数目的内存页
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 static struct Page *default_alloc_pages (size_t n) { assert(n > 0 ); if (n > nr_free) { return NULL ; } struct Page *page = NULL ; list_entry_t *le = &free_list; while ((le = list_next(le)) != &free_list) { struct Page *p = le2page(le, page_link); if (p->property >= n) { page = p; break ; } } if (page != NULL ) { list_del(&(page->page_link)); if (page->property > n) { struct Page *p = page + n; p->property = page->property - n; list_add(&free_list, &(p->page_link)); } nr_free -= n; ClearPageProperty(page); } return page; }
首先检查空闲页的总数目和所需数目的关系
然后采用 first-fit 算法来获取合适空闲页
最后检查该空闲块是否剩余,如果剩余直接插到链表头部
default_free_pages: 释放目标n个内存页
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 static void default_free_pages (struct Page *base, size_t n) { assert(n > 0 ); struct Page *p = base; for (; p != base + n; p ++) { assert(!PageReserved(p) && !PageProperty(p)); p->flags = 0 ; set_page_ref(p, 0 ); } base->property = n; SetPageProperty(base); list_entry_t *le = list_next(&free_list); while (le != &free_list) { p = le2page(le, page_link); le = list_next(le); if (base + base->property == p) { base->property += p->property; ClearPageProperty(p); list_del(&(p->page_link)); } else if (p + p->property == base) { p->property += base->property; ClearPageProperty(base); base = p; list_del(&(p->page_link)); } } nr_free += n; list_add(&free_list, &(base->page_link)); }
先把将要被释放的内存页的各个字段置空
然后遍历整个链表,合并相邻的空闲页
最后更新空闲页数目,并且把合并后的空闲页插入到链表的头部
修改 ucore 的代码:
问题的关键就在于“剩余空闲页插入链表头”这一过程
first-fit 算法要求将空闲内存块按照地址从小到大的方式 连起来,那么“插入链表头”的操作想必会影响链表的物理地址次序
所以在 default_alloc_pages 和 default_free_pages 中关于“插入链表头”的操作都要修改
default_alloc_pages: (修改后)
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 static struct Page *default_alloc_pages (size_t n) { assert(n > 0 ); if (n > nr_free) { return NULL ; } struct Page *page = NULL ; list_entry_t *le = &free_list; while ((le = list_next(le)) != &free_list) { struct Page *p = le2page(le, page_link); if (p->property >= n) { page = p; break ; } } if (page != NULL ) { if (page->property > n) { struct Page *p = page + n; p->property = page->property - n; list_add(&(page->page_link), &(p->page_link)); } list_del(&(page->page_link)); nr_free -= n; ClearPageProperty(page); } return page; }
default_free_pages: (部分&修改后)
1 2 3 4 5 6 7 8 9 for (le = list_next(&free_list); le != &free_list; le = list_next(le)){ p = le2page(le, page_link); if (base + base->property <= p) { assert(base + base->property != p); break ; } } list_add_before(le, &(base->page_link));
练习2- 实现寻找虚拟地址对应的页表项 通过设置页表和对应的页表项,可建立虚拟内存地址和物理内存地址的对应关系
get_pte
函数是设置页表项环节中的一个重要步骤,此函数找到一个虚地址对应的二级页表项的内核虚拟地址,如果此二级页表项不存在,则分配一个包含此项的二级页表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 pte_t * get_pte(pde_t *pgdir, uintptr_t la, bool create) { #if 0 pde_t *pdep = NULL ; if (0 ) { uintptr_t pa = 0 ; } return NULL ; #endif }
要求:
查找页面目录条目
检查输入是否不存在
检查是否需要创建,然后为页表分配页
设置页面参考
获取页面的线性地址
使用 memset 清除页面内容
设置页面目录项的权限
返回页表项
接下来就要完善这个函数:
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 pte_t * get_pte(pde_t *pgdir, uintptr_t la, bool create) { #if 0 pde_t *pdep = NULL ; if (0 ) { uintptr_t pa = 0 ; } return NULL ; #endif pde_t *pdep = &pgdir[PDX(la)]; if (!(*pdep & PTE_P)) { struct Page *page ; if (!create || (page = alloc_page()) == NULL ) { return NULL ; } set_page_ref(page, 1 ); uintptr_t pa = page2pa(page); memset (KADDR(pa), 0 , PGSIZE); *pdep = pa | PTE_U | PTE_W | PTE_P; } return &((pte_t *)KADDR(PDE_ADDR(*pdep)))[PTX(la)]; }
练习3-释放某虚地址所在的物理页并取消对应的二级页表项映射 当释放一个包含某虚地址的物理内存页时,需要让对应此物理内存页的管理数据结构 Page 做相关的清除处理,使得此物理内存页成为空闲,另外还需把表示虚地址与物理地址对应关系的二级页表项清除
我们的任务就是补全一下这个函数:
1 2 3 4 5 6 7 8 static inline void page_remove_pte (pde_t *pgdir, uintptr_t la, pte_t *ptep) {#if 0 if (0 ) { struct Page *page = NULL ; } #endif }
要求:
检查此页表条目是否存在
找到与 pte 对应的页面
减少页面引用
并在页面引用达到0时释放此页面
清除第二页表格条目
齐平 tlb
接下来就完善这个函数:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #define free_page(page) free_pages(page, 1) void free_pages (struct Page *base, size_t n) { bool intr_flag; local_intr_save(intr_flag); { pmm_manager->free_pages(base, n); } local_intr_restore(intr_flag); } static inline int page_ref_dec (struct Page *page) { page->ref -= 1 ; return page->ref; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 static inline void page_remove_pte (pde_t *pgdir, uintptr_t la, pte_t *ptep) { #if 0 if (0 ) { struct Page *page = NULL ; } #endif if (*ptep & PTE_P) { struct Page *page = pte2page(*ptep); if (page_ref_dec(page) == 0 ) { free_page(page); } *ptep = 0 ; tlb_invalidate(pgdir, la); } }
最终结果:
1 2 3 4 5 6 ➜ lab2 make grade Check PMM: (2.2 s) -check pmm: OK -check page table: OK -check ticks: OK Total Score: 50 /50