Lab2 物理内存管理
实验目的
- 理解基于段页式内存地址的转换机制
- 理解页表的建立和使用方法
- 理解物理内存的管理方法
实验内容
uCore Lab 2 – 物理内存管理
- 编译运行 uCore Lab 2 的工程代码；
- 完成 uCore Lab 2 练习 1-3 的编程作业；
- 思考如何实现 uCore Lab 2 扩展练习 1-2。
编译运行 uCore Lab 2 的工程代码
在文件夹下终端输入
make
，即可完成编译。
就编译成功了。
练习1：实现 first-fit 连续物理内存分配算法（需要编程）
在实现first fit 内存分配算法的回收函数时，要考虑地址连续的空闲块之间的合并操作。提示:在建立空闲页块链表时，需要按照空闲页块起始地址来排序，形成一个有序的链表。可能会修改default_pmm.c中的default_init，default_init_memmap，default_alloc_pages， default_free_pages等相关函数。请仔细查看和理解default_pmm.c中的注释。
注释中Prepare部分，需要我学会用
list_init, list_add(list_add_after), list_add_before, list_del, list_next, list_prev
操作。
参看
list.h
结构体为
struct list_entry {
struct list_entry *prev, *next;
};
一个指向前驱和一个指向后继的指针
分别阅读函数，功能大致如下
list_init初始化一个新的list_entry
list_add，list_add_after和list_add_after都是添加一个新的条目
list_del是 删除一个条目
list_del_init 从表中删除一个条目并重定义它
list_empty 判断列表是否为空
list_next 获取列表的前一项
list_prev 获取列表的后一项
阅读下面注释，在memlayout.h中找到Page的定义
struct Page {
int ref; // page frame's reference counter
uint32_t flags; // array of flags that describe the status of the page frame
unsigned int property; // the num of free block, used in first fit pm manager
list_entry_t page_link; // free list link
};
再根据github上实验的说明
ref：表示这页被页表的引用记数，如果这个页被页表引用了，即在某页表中有一个页表项设置了一个虚拟页到这个Page管理的物理页的映射关系，就会把Page的ref加一；反之，若页表项取消，即映射关系解除，就会把Page的ref减一。
/* Flags describing the status of a page frame */
#define PG_reserved 0 // the page descriptor is reserved for kernel or unusable
#define PG_property 1 // the member 'property' is valid
这表示flags目前用到了两个bit表示页目前具有的两种属性，bit 0表示此页是否被保留（reserved），如果是被保留的页，则bit 0会设置为1，且不能放到空闲页链表中，即这样的页不是空闲页，不能动态分配与释放。比如目前内核代码占用的空间就属于这样“被保留”的页。在本实验中，bit 1表示此页是否是free的，如果设置为1，表示这页是free的，可以被分配；如果设置为0，表示这页已经被分配出去了，不能被再二次分配。另外，本实验这里取的名字PG_property比较不直观，主要是我们可以设计不同的页分配算法（best fit, buddy system等），那么这个PG_property就有不同的含义了。
property用来记录某连续内存空闲块的大小。
成员变量page_link是便于把多个连续内存空闲块链接在一起的双向链表指针
据注释，有种“tricky method”可以强制转换列表为页指针，即
#define le2page(le, member)
to_struct((le), struct Page, member)
First-Fit(首次适应算法)
是顺序查找到一个满足要求的就分配。如果空间明显大于要求，通常会切割，并把剩下的放回去。会有外部碎片
default_init
#define nr_free (free_area.nr_free)
static void
default_init(void) {
list_init(&free_list);
nr_free = 0;
}
typedef struct {
list_entry_t free_list;
unsigned int nr_free;
} free_area_t;
nr_free表示空闲页的数量，这个函数应该不用修改。
default_init_memmap
根据注释调用路径
kern_init
–>
pmm_init
–>
page_init
–>
init_memmap
–> *
pmm_manager
–>
init_memmap
.
set_page_ref(page,1) : means the page be referenced by one time
set_page_ref可以清除引用此页的虚拟页个数
可以重写成
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_before(&free_list, &(base->page_link));
}
函数先声明一个base的Page，再生成base为起始地址的n个页
如果有保留页，就终止程序
对每页都设置标志为Property为1
被引用次数ref为0
接好双向指针
退出循环后，使空闲页总数加n
base的连续空闲页数为n
default_alloc_pages()
根据注释，我要从free链表指针开始往后找，找到第一个property >=n列表地址，重写安排剩余块的大小，并返回分配出去的块的地址。
根据前面的代码，可知
le2page
宏可以由链表元素获得对应的Page指针
注释讲得非常详细，一步步写即可，找不到就返回NULL
改写后的函数
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;
SetPageProperty(p);
list_add_after(&(page->page_link), &(p->page_link));
}
list_del(&(page->page_link));
nr_free -= n;
ClearPageProperty(page);
}
return page;
}
顺着指针向后找，找到第一个后续有联系n个空闲页的位置。然后枚举这n个空闲页，设置它们不空闲了，并且后续没有连续页了。并且可以这对于这n块的链表删去。
若这个链表其实有超过n页，则把剩下的加回去。返回分配的n个页的起始地址p。若没有，最后返回NULL。
default_free_pages
根据注释，重新链接这些页到自由页链表，也许可以合并小的链表项并成大的
修改后如下
static void
default_free_pages(struct Page *base, size_t n) {
assert(n > 0);
assert(PageReserved(base));
list_entry_t *le = &free_list;
struct Page * p;
while((le=list_next(le)) != &free_list) {
p = le2page(le, page_link);
if(p>base){
break;
}
}
for(p=base;p<base+n;p++){
list_add_before(le, &(p->page_link));
}
base->flags = 0;
set_page_ref(base, 0);
ClearPageProperty(base);
SetPageProperty(base);
base->property = n;
p = le2page(le,page_link) ;
if( base+n == p ){
base->property += p->property;
p->property = 0;
}
le = list_prev(&(base->page_link));
p = le2page(le, page_link);
if(le!=&free_list && p==base-1){
while(le!=&free_list){
if(p->property){
p->property += base->property;
base->property = 0;
break;
}
le = list_prev(le);
p = le2page(le,page_link);
}
}
nr_free += n;
return ;
}
首先遍历链表，找到这些页应该插入的位置
然后把n个页依次插入，插入时设置下flags为0，被引用次数ref为0
base的property可设为n，标志这里开始有n页连续可用
然后尝试合并base与后续的一块
然后设le为该页的前一页，将le向free链表头枚举，尝试向前合并，即将自己的property转移到前一页上，相当于resize了整个链表。
最后空闲页数加n。
first fit算法是否有进一步的改进空间
在分配与释放内存时，在双向链表上操作复杂度为O(n)，可以用线段树等树形结构维护，在分配过程为一次二分查找，但仍需分配处理分配的N个页，复杂度仍是O(N)。FREE时直接二分查找即可，复杂度O(logn)。
也可以使用朴素的分块算法，每个块大小为sqrt(总空间)维护自己负责的块头和块尾指针，分配与释放复杂度均为O(sqrt(n))
练习2：实现寻找虚拟地址对应的页表项（需要编程）
通过设置页表和对应的页表项，可建立虚拟内存地址和物理内存地址的对应关系。其中的get_pte函数是设置页表项环节中的一个重要步骤。此函数找到一个虚地址对应的二级页表项的内核虚地址，如果此二级页表项不存在，则分配一个包含此项的二级页表。本练习需要补全get_pte函数 in kern/mm/pmm.c，实现其功能。请仔细查看和理解get_pte函数中的注释。get_pte函数的调用关系图如下所示：
根据实验说明的科普，地址分为逻辑地址（虚地址）、线性地址和物理地址。
逻辑地址是指令使用的地址。
物理地址是实际在内存中的地址。
段页式结构中，
逻辑地址通过段式管理的映射得到线性地址，线性地址通过页式管理映射得到物理地址。
get_pte的功能是得到线性地址（在二级页表中对应的项）
参看注释，让我先读pmm.h，了解一些宏。
struct pmm_manager {
const char *name; // XXX_pmm_manager's name
void (*init)(void); // initialize internal description&management data structure
// (free block list, number of free block) of XXX_pmm_manager
void (*init_memmap)(struct Page *base, size_t n); // setup description&management data structcure according to
// the initial free physical memory space
struct Page *(*alloc_pages)(size_t n); // allocate >=n pages, depend on the allocation algorithm
void (*free_pages)(struct Page *base, size_t n); // free >=n pages with "base" addr of Page descriptor structures(memlayout.h)
size_t (*nr_free_pages)(void); // return the number of free pages
void (*check)(void); // check the correctness of XXX_pmm_manager
};
有个核心结构体用作物理内存分配，即前一个练习实现的功能，有初始化，分配，释放等功能。
注释里简单介绍了些宏
KADDR可以从物理地址得到内核虚拟地址
PADDR可以从内核虚地址得到物理地址
PTE_P 0x001 表示物理内存页存在
PTE_W 0x002 表示物理内存页内容可写
PTE_U 0x004 表示可以读取对应地址的物理内存页内容
其中KADDR如下，实验说明也有涉及，主要方法就是加上内核基址。
#define KADDR(pa) ({ \
uintptr_t __m_pa = (pa); \
size_t __m_ppn = PPN(__m_pa); \
if (__m_ppn >= npage) { \
panic("KADDR called with invalid pa %08lx", __m_pa); \
} \
(void *) (__m_pa + KERNBASE); \
})
根据mmu.h中的注释，页式管理将32位的线性地址拆分为高10位，Directory，中10位Table和低12位Offset三部分。
Directory即一级页表
PDX(la)可以获取Directory
Table为二级页表
PTX(la)可以获取Table
改写的get_pte函数如下
pte_t *
get_pte(pde_t *pgdir, uintptr_t la, bool create) {
#if 0
pde_t *pdep = NULL; // (1) find page directory entry
if (0) { // (2) check if entry is not present
// (3) check if creating is needed, then alloc page for page table
// CAUTION: this page is used for page table, not for common data page
// (4) set page reference
uintptr_t pa = 0; // (5) get linear address of page
// (6) clear page content using memset
// (7) set page directory entry's permission
}
return NULL; // (8) return page table entry
#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)];
}
先用PDX获取一级页表的位置，如果成功就可以直接返回
根据create位判断是否创建这个二级页表，若为0则不创建，否则创建。
将这页引用次数+1，并得到该页的物理地址
随后用
KADDR
转换为虚拟地址并初始化
设置下控制位
最后返回这个页表所对应的线性地址。
请描述页目录项（Page Directory Entry）和页表项（Page Table Entry）中每个组成部分的含义以及对ucore而言的潜在用处。
根据注释，页表目录项有这些标志
PTE_P 存在位
PTE_W 是否可写
PTE_U 该页访问需要的特权级
PTE_PWT 是否使用write through存储方法
PTE_PCD 若为1则不对该页进行缓存
PTE_A 该页是否被使用过
PTE_D 脏位
PTE_PS 设置Page大小
PTE_MBZ 恒为0
剩下的9~11位未被CPU使用可以OS支配
根据理论课知识
PDE的高二十位为PDE对应的页表起始位置。
PTE的高二十位为PTE指向的物理页的物理地址。
根据理论课知识，页表项由页号，页框号，页帧地址等组成
有存在位，读写有效位，访问权限位，脏位，系统程序使用有效位，和一些没有定义的标记。
对ucore的用处
页目录项和页表项中的保留位可以帮助ucore实现功能的扩展，可以建立数据结构，实现LRU之类的内存管理算法，页置换算法，和cache等配合等。
如果ucore执行过程中访问内存，出现了页访问异常，请问硬件要做哪些事情？
- 保存发生页访问异常的地址保存到寄存器中
- 设置错误代码，并切换到内核态；
- 引发Page Fault，根据中断描述符表查询到对应Page Fault的中断服务程序ISR，跳转到对应的ISR处执行，由软件进行Page Fault处理，将外存的数据换到内存中；
- 处理完后上下文切换，返回中断之前的状态
练习3：释放某虚地址所在的页并取消对应二级页表项的映射（需要编程）
函数调用关系如下
注释讲了一些数据结构及注释的含义
struct Page *page pte2page(*ptep)：获取对应的物理页
free_page：释放一页
page_ref_dec(page)：引用数减一，并返回引用数，若引用数为0，则释放
tlb_invalidate(pde_t *pgdir, uintptr_t la)：无效一个TLB的访问，如果它在被使用
PTE_P 0x001：位1，表示物理内存页存在
函数如下
static inline void
page_remove_pte(pde_t *pgdir, uintptr_t la, pte_t *ptep) {
#if 0
if (0) { //(1) check if page directory is present
struct Page *page = NULL; //(2) find corresponding page to pte
//(3) decrease page reference
//(4) and free this page when page reference reachs 0
//(5) clear second page table entry
//(6) flush tlb
}
#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，若为0则把它释放，清除页目录项，如果修改的页表正在使用，则无效
数据结构Page的全局变量（其实是一个数组）的每一项与页表中的页目录项和页表项有无对应关系？如果有，其对应关系是啥？
每个页目录项记录了一个页表项的信息，一个页表项也记录一个物理页的信息。
数据结构Page的全局变量的每一项记录的也是一个物理页的信息。
则页目录项和页表项中所存的物理页地址就是Page的全局变量的某一页。
所以有对应关系
如果希望虚拟地址与物理地址相等，则需要如何修改lab2，完成此事？ 鼓励通过编程来具体完成这个问题
lab2中建立了从虚拟地址到物理地址的映射，那么只需要取消映射，就可以实现虚拟地址以及物理地址相等。
因为根据LAB1的ld链接方式，虚拟地址与物理地址都是从
0x100000
开始。
可以在kernal.ld中，将链接脚本的0xC0100000改为0x100000，再把偏移量
KERNBASE
改为0即可。
实验结果
输入make qemu
能成功分配内存，实现first fit
输入 make grade
说明代码能实现相应的功能
扩展练习Challenge：buddy system（伙伴系统）分配算法（需要编程）
Buddy System算法把系统中的可用存储空间划分为存储块(Block)来进行管理, 每个存储块的大小必须是2的n次幂(Pow(2, n)), 即1, 2, 4, 8, 16, 32, 64, 128…
可以用树状数组的方式存储内存，每种块的数量是是固定的，但实际分配又可以调整。
树状数组结构如下所示
每个数字所代表的块的大小为该数字二进制中，最低位的1的权重。故每个块虽然大小不同，但可以存在同一个线性空间中，地址转化方便。
每个块不仅要维护自己的存在位，脏位等信息，还有整合维护自己对应的线段所覆盖的块的信息。
申请分配时，可以随机一个位置i，每次向上跳，即i+=i&-i
找到一个刚好能放下的块就停止，返回这个块的地址。复杂度log(N）
释放时可直接找到这个块，但同样要log(N)时间修改覆盖这个块的块的信息。
（不保证正确性）
扩展练习Challenge：任意大小的内存单元slub分配算法（需要编程）
这其实是linux内核中比较成熟的算法，但我还是不能理解它的精髓。
单个物理页内分配小内存用slub分配，页级别的物理内存用buddy系统分配
SLAB 分配器为每种使用的内核对象建立单独的缓冲区。
每种缓冲区由多个 slab 组成，每个 slab就是一组连续的物理内存页框，被划分成了固定数目的对象。
根据对象大小的不同，缺省情况下一个 slab 最多可以由 1024 个物理内存页框构成。
内核使用 kmem_cache 数据结构管理缓冲区。
由于 kmem_cache 自身也是一种内核对象，所以需要一个专门的缓冲区。
所有缓冲区的 kmem_cache 控制结构被组织成以 cache_chain 为队列头的一个双向循环队列，同时 cache_cache 全局变量指向kmem_cache 对象缓冲区的 kmem_cache 对象。
每个 slab 都需要一个类型为 struct slab 的描述符数据结构管理其状态，同时还需要一个 kmem_bufctl_t（被定义为无符号整数）的结构数组来管理空闲对象。
如果对象不超过 1/8 个物理内存页框的大小，那么这些 slab 管理结构直接存放在 slab 的内部，位于分配给 slab 的第一个物理内存页框的起始位置；否则的话，存放在 slab 外部，位于由 kmalloc 分配的通用对象缓冲区中。