0%

Ucore-Lab2

项目组成

相对与实验一,实验二主要增加和修改的文件如上表所示。主要改动如下:

  • 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: 112KB
memory management: default_pmm_manager
e820map:
memory: 0009fc00, [00000000, 0009fbff], type = 1.
memory: 00000400, [0009fc00, 0009ffff], type = 2.
memory: 00010000, [000f0000, 000fffff], type = 2.
memory: 07ee0000, [00100000, 07fdffff], type = 1.
memory: 00020000, [07fe0000, 07ffffff], 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; /* list_entry其实是两个指针 */
};

typedef struct list_entry list_entry_t;

/* *
* struct Page - Page descriptor structures. Each Page describes one
* physical page. In kern/mm/pmm.h, you can find lots of useful functions
* that convert Page to other data types, such as phyical address.
* */
struct Page {
int ref; // 当前页被引用的次数,与内存共享有关
uint32_t flags; // 标志位的集合,与eflags寄存器类似
unsigned int property; // 空闲的连续page数量,这个成员只会用在连续空闲page中的第一个page
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 - Present:表示当前PTE所指向的物理页面是否驻留在内存中
  • 1 - Writeable:表示是否允许读写
  • 2 - User:表示该页的访问所需要的特权级(即User(ring 3)是否允许访问)
  • 3 - PageWriteThough:表示是否使用write through缓存写策略
  • 4 - PageCacheDisable:表示是否 不对 该页进行缓存
  • 5 - Access:表示该页是否已被访问过
  • 6 - Dirty:表示该页是否已被修改
  • 7 - PageSize:表示该页的大小
  • 8 - MustBeZero:该位必须保留为0
  • 9-11 - Available:第9-11这三位并没有被内核或中断所使用,可保留给OS使用
  • 12-31 - Offset:目标地址的后20位

uCore物理页链表

结构体 free_area_t:用于定义两个关键的全局变量

1
2
3
4
5
/* free_area_t - 维护一个双向链表来记录空闲(未使用的)页 */
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; /* 指向next */
}

static inline void /* list_add是list_add_after的外包装 */
list_add(list_entry_t *listelm, list_entry_t *elm) {
// listelm: 目标链表结点
// elm: 将要插入的对象(list_entry_t *elm == NULL)
list_add_after(listelm, elm);
}

/* 结点->prev <--1--> 结点 <--2--> 结点->next */

static inline void /* 插入"2"号位置 */
list_add_after(list_entry_t *listelm, list_entry_t *elm) {
__list_add(elm, listelm, listelm->next);
}

static inline void /* 插入"1"号位置 */
list_add_before(list_entry_t *listelm, list_entry_t *elm) {
__list_add(elm, listelm->prev, listelm);
}

static inline void /* 正真执行添加操作的是__list_add */
__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_del的外包装 */
list_del(list_entry_t *listelm) {
__list_del(listelm->prev, listelm->next);
}

static inline void /* 正真执行脱链操作的是__list_del */
__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)
/* 获取"页目录项PDE"的索引:用来在页目录中定位一个页表 */

#define PTXSHIFT 12
#define PTX(la) ((((uintptr_t)(la)) >> PTXSHIFT) & 0x3FF)
/* 获取"页表项PTE"的索引:用来在页表中定位具体的物理页 */

还有一些关于内存管理的宏定义:

  • 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) {
/* base:基地址,n:表示要初始化n个页 */
assert(n > 0); /* 断言表达式"n>0"成立,否则调用panic来终止程序 */
struct Page *p = base;
for (; p != base + n; p ++) {
assert(PageReserved(p)); /* 进行检查(这里不需要关心) */
p->flags = p->property = 0; /* 设置flags & 置空property(只有base page的property才会起作用) */
set_page_ref(p, 0); /* 设置该物理页面的引用次数为0 */
}
base->property = n; /* 在base page中设置空闲的连续page数量 */
SetPageProperty(base); /* 设置当前页为空闲 */
nr_free += n; /* nr_free:空闲页的总数 */
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) {
/* n:表示要分配n个页 */
assert(n > 0); /* 断言表达式"n>0"成立,否则调用panic来终止程序 */
if (n > nr_free) {
return NULL; /* 申请内存页的数目>空闲内存页的数目 */
}
struct Page *page = NULL;
list_entry_t *le = &free_list; /* 初始化le为链表头部 */
while ((le = list_next(le)) != &free_list) { /* 实现first-fit算法 */
struct Page *p = le2page(le, page_link); /* 根据链表信息获取该page的位置 */
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; /* 更新base page->property */
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) {
/* base:基地址,n:表示要初始化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; /* 更新base page->property */
SetPageProperty(base); /* 设置当前页为空闲 */
list_entry_t *le = list_next(&free_list); /* 初始化le为链表头部 */
while (le != &free_list) { /* 遍历整个链表,找寻是否有相邻的空闲页 */
p = le2page(le, page_link); /* 根据链表信息获取该page的位置 */
le = list_next(le);
if (base + base->property == p) { /* 在base的高地址处有相邻的空闲页 */
base->property += p->property; /* 合并空闲页,更新base page->property */
ClearPageProperty(p); /* 将被合并的空闲页标记为不可用 */
list_del(&(p->page_link)); /* 脱链 */
}
else if (p + p->property == base) { /* 在base的低地址处有相邻的空闲页 */
p->property += base->property;
ClearPageProperty(base);
base = p; /* 更新base */
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 * /* 获取pte(页表项,页表) */
get_pte(pde_t *pgdir, uintptr_t la, bool create) {
// pgdir:进程自己页表的虚拟地址,将在进程创建页表时为其赋值
// la:线性地址,虚拟地址
// create:信息标记位,根据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 * /* 获取pte(页表项,页表) */
get_pte(pde_t *pgdir, uintptr_t la, bool create) {
// pgdir:进程自己页表的虚拟地址,将在进程创建页表时为其赋值
// la:线性地址,虚拟地址
// create:信息标记位,根据create位判断是否创建这个二级页表

#if 0
pde_t *pdep = NULL;
if (0) {
uintptr_t pa = 0;
}
return NULL;
#endif
pde_t *pdep = &pgdir[PDX(la)];
/* 根据la(线性地址,虚拟地址)利用PDX获取对应"页目录项PDE的索引" */
/* 放入pgdir(进程自己一级页表的虚拟地址)中,索引出对应"页目录项PDE的物理地址" */

if (!(*pdep & PTE_P)) { /* 如果这个物理内存页pdep不存在 */
struct Page *page;
if (!create || (page = alloc_page()) == NULL) {
/* 检查是否需要创建 || 检查alloc_page()是否分配成功 */
return NULL;
}
set_page_ref(page, 1); // 要查找该页表,则引用次数+1
uintptr_t pa = page2pa(page); // 得到该页的物理地址
memset(KADDR(pa), 0, PGSIZE); // 利用KADDR转成虚拟地址,并初始化
*pdep = pa | PTE_U | PTE_W | PTE_P; // 设置页面目录项的权限(存在,可读,可写)
}
return &((pte_t *)KADDR(PDE_ADDR(*pdep)))[PTX(la)];
// 用KADDR返回二级页表所对应的虚拟地址
}

练习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; /* page->ref:当前页被引用的次数,与内存共享有关 */
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) {
// pgdir:进程自己页表的虚拟地址,将在进程创建页表时为其赋值
// la:线性地址,虚拟地址
// 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); /* 刷新TLB内的数据 */
}
}

最终结果:

1
2
3
4
5
6
➜  lab2 make grade
Check PMM: (2.2s)
-check pmm: OK
-check page table: OK
-check ticks: OK
Total Score: 50/50