ucore是清华大学提供的一个学习操作系统的平台。ucore有完整的mooc视频与说明文档。
本文将主要记录在完成ucore平台的实验时，个人认为ucore内核及Result中的存在的问题，以及部分挑战练习内容。由于个人水平有限，可能理解有误，欢迎前来讨论。
本文主要内容：
- Lab2 物理内存管理 练习一 Result代码错误
- Lab3 虚拟内存管理 挑战练习 Clock算法实现
- Lab8 文件系统 内核错误 用户程序
ls错误
Lab2 练习一 Result代码错误
在实现first fit 内存分配算法的回收函数时，要考虑地址连续的空闲块之间的合并操作。提示:在建立空闲页块链表时，需要按照空闲页块起始地址来排序，形成一个有序的链表。
ans中思路是把所有的空闲页都加入空闲列表，这样效率非常低，且其中有很多标志位置位错误。我选择使用类似于实验指导书上的思路，将一个空闲块中的一个空闲页加入到空闲列表中。所有的操作只是对空闲段里面的第一个空闲页的操作。
代码中详细的注释，这里不做过多的说明。
/*
* Details of FFMA
* Prepare: In order to implement the First-Fit Mem Alloc (FFMA), we should manage the free mem block use some list.
* 为了能够接入FFMA我们要先建立空闲列表
* The struct free_area_t is used for the management of free mem blocks.
* free_area_t是空闲列表的中的结构体
* At first you should be familiar to the struct list in list.h.
* struct list is a simple doubly linked list implementation.
* 首先要在list.h找到list结构体
* list是一个双向链表
* You should know howto USE: list_init, list_add(list_add_after), list_add_before, list_del, list_next, list_prev
* 嗨呀就是简单的链表操作
* Another tricky method is to transform a general list struct to a special struct (such as struct page):
* you can find some MACRO: le2page (in memlayout.h), (in future labs: le2vma (in vmm.h), le2proc (in proc.h),etc.)
* 可以吧list的结构体转为page|proc的结构体
**/
free_area_t free_area;
#define free_list (free_area.free_list)
#define nr_free (free_area.nr_free)
/**
* default_init:
* you can reuse the demo default_init fun to
* init the free_list and set nr_free to 0.
* 代码已经实现了 init freelist 然后设置nr_free 为0
* free_list : is used to record the free mem blocks.
* nr_free : is the total number for free mem blocks.
*/
static void default_init(void) {
list_init(&free_list);
nr_free = 0;
}
/**
* default_init_memmap:
* 调用顺序: kern_init --> pmm_init-->page_init-->init_memmap--> pmm_manager->init_memmap
* This fun is used to init a free block (with parameter: addr_base, page_number).
* 这个函数是用来初始化一个free block 参数有base和page_number
* 若本页是空的 且不是第一页，flag中的property位设置为0
* 若本页是空的 且是第一页，flag中的property位设置为1 说明其有效
* 若本页空 且是第一页 property就是总共的空block数
* reference 引用的count清0 也就是有没有对应咯
**/
static void default_init_memmap(struct Page *base, size_t n) {
//assert用来检查一个判断是否为真
assert(n > 0);
struct Page *p = base;
for (; p != base + n; p++) {
p->flags = 0;
//若本页空&&不是第一页,property就是总共的空block数
p->property = 0;
//reference引用的count清0
p->ref = 0;
ClearPageReserved(p);
// from memlayout
// if this bit=1:
// the Page is reserved for kernel,
// cannot be used in alloc/free_pages;
// otherwise, this bit=0
}
//跟新一共有多少个free page
nr_free += n;
//first block
SetPageProperty(base);
//若本页空&&第一页,property就是总共的空block数
base->property = n;
list_add(&free_list, &(base->page_link));
}
/**
* default_alloc_pages:
* search find a first free block (block size >=n)
* in free list and reszie the free block,
* return the addr of malloced block.
**/
static struct Page *
default_alloc_pages(size_t n) {
list_entry_t *list_iterator, *nxtptr;
struct Page *first_fit_page;
assert(n > 0);
//要分配的页数大于剩余的free数
if (n > nr_free) {
return NULL;
}
list_iterator = &free_list;
//循环访问一次free list
while ((list_iterator = list_next(list_iterator)) != &free_list) {
//从link回去找到page的base addr
first_fit_page = le2page(list_iterator, page_link);
//若当前的page可用大于需要的size
//注意这个地方，只有一个空闲区域里面的first page才会有property的data
if (first_fit_page->property >= n) {
//将这片空闲区域中的n个block分配出去
//检查这n个block能否分配
struct Page *alloc = first_fit_page;
for (; alloc != first_fit_page + n; alloc++) {
//若Reserved位为1 不能alloc和free
assert(!PageReserved(alloc));
}
//若这个空闲区域里面空闲的数量比我需要的数量还要多
if (first_fit_page->property > n) {
//原来空闲的空间这样子 H是空闲区域里面first page
//||H1....................x..................||
//现在这个空闲的区域变成了这样子
//.......n.......||H2........x-n.............||
//设置其property为剩下的x-n个block
//向后找n个page后的page
struct Page *new_head = first_fit_page + n;
new_head->property = first_fit_page->property - n;
SetPageProperty(new_head);
//因为按照addr的order 则直接添加到first fit page的后面就好了
list_add(&(first_fit_page->page_link), &(new_head->page_link));
}
//从free list 中删除分配走的page的link
list_del(&(first_fit_page->page_link));
ClearPageProperty(first_fit_page);
nr_free -= n;
return first_fit_page;
}
}
return NULL;
}
/**
* default_free_pages
* free掉分配了的页
* base：为free的页的first page的基地址
* n ：为free掉多少页
*/
static void default_free_pages(struct Page *base, size_t n) {
assert(n > 0);
struct Page *p = base;
//将n这么多空间释放
for (; p != base + n; p++) {
//检查要free的n个size时候合法
//不能被标记Reserved和Property
assert(!PageReserved(p) && !PageProperty(p));
//初始化flags位
p->flags = 0;
//清空页面访问counter
set_page_ref(p, 0);
}
//更新新的base
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);
//若base后面接着了p
if (base + base->property == p) {
base->property += p->property;
p->property = 0;
ClearPageProperty(p);
list_del(&(p->page_link));
}
//若p后面接着了base
else if (p + p->property == base) {
p->property += base->property;
ClearPageProperty(base);
base->property = 0;
base = p;
list_del(&(p->page_link));
}
}
// 按照地址顺序插入这个新的base节点
nr_free += n;
le = list_next(&free_list);
while (le != &free_list) {
p = le2page(le, page_link);
if (p > base)
break;
le = list_next(le);
}
//插入到list中去
list_add_before(le, &(base->page_link));
}
static size_t default_nr_free_pages(void) {
return nr_free;
}Lab3 挑战练习 Clock算法实现
设定swap策略为Clock算法
/*
* 设定swap策略
*/
struct swap_manager swap_manager_clock = {
.name = "clock clock manager",
.init = &_clock_init,
.init_mm = &_clock_init_mm,
.tick_event = &_clock_tick_event,
.map_swappable = &_clock_map_swappable,
.set_unswappable = &_clock_set_unswappable,
.swap_out_victim = &_clock_swap_out_victim,
.check_clock_swap = &_clock_check_swap,
};选择调用clock算法
#ifdef CLOCK
sm = &swap_manager_clock;
#else
sm = &swap_manager_fifo;
#endif由于每次我们访问一个地址时，要对物理页做标记，所以要用到mm中的pd的基地址，从而获取pte，获取page对象，再对dirty位做标记，这里在抽象类中添加一个方法（mm是拥有相同PDT）
int (*check_clock_swap)(struct mm_struct *mm);在接入该接口时添加调用的mm参数
static inline int check_content_access(struct mm_struct *mm){
#ifdef CLOCK
int ret = sm->check_clock_swap(mm);
return ret;
#else
int ret = sm->check_swap();
return ret;
#endif
}在page的结构体中flag标志位加入dirtybit
#define PG_dirtybit 2 // Used for clock pra
#define SetDirtyBit(page) set_bit(PG_dirtybit, &((page)->flags))
#define ClearDirtyBit(page) clear_bit(PG_dirtybit, &((page)->flags))
#define PageDirty(page) test_bit(PG_dirtybit,&((page)->flags))CLOCK实现
#include <defs.h>
#include <x86.h>
#include <stdio.h>
#include <string.h>
#include <swap.h>
#include <swap_clock.h>
#include <list.h>
list_entry_t pra_list_head;
static int _clock_init_mm(struct mm_struct *mm) {
list_init(&pra_list_head);
mm->sm_priv = &pra_list_head;
return 0;
}
static int _clock_map_swappable(struct mm_struct *mm, uintptr_t addr,
struct Page *page, int swap_in) {
list_entry_t *head = (list_entry_t*) mm->sm_priv;
list_entry_t *entry = &(page->pra_page_link);
assert(entry != NULL && head != NULL);
//将entry加入到list的头
list_add(head->prev, entry);
//page->has_used = 1;
SetDirtyBit(page);
//init present_ptr
if(mm->present_ptr == NULL){
//cprintf("INIT\n\n\n\n");
mm->present_ptr = entry;
}
return 0;
}
static int _clock_swap_out_victim(struct mm_struct *mm, struct Page ** ptr_page,
int in_tick) {
list_entry_t *head = (list_entry_t*) mm->sm_priv;
list_entry_t *tmp;
struct Page *iter;
assert(head != NULL);
assert(in_tick == 0);
//cprintf("Present PTR %x\n", mm->present_ptr);
cprintf("\nLet's find victim!!!\n");
//list empty
assert(head -> next != head);
while(1){
//若转了一圈回到了head 跳过head
if(mm->present_ptr == head) {
cprintf("Hit head!\n");
mm->present_ptr = mm->present_ptr->next;
}
iter = le2page(mm->present_ptr,pra_page_link);
//若标记dirtybit为0就替换走
if(!PageDirty(iter)) {
cprintf("Find it!!!\n\n");
tmp = mm->present_ptr;
mm->present_ptr = mm->present_ptr->next;
*ptr_page = iter;
list_del(tmp);
return 0;
}
cprintf("Not good\n");
ClearDirtyBit(iter);
mm->present_ptr = mm->present_ptr->next;
}
return 1;
}
static void visit(struct mm_struct *mm,uintptr_t addr,int value){
*(unsigned char*) addr = value;
//从虚拟地址获取pte
uintptr_t *tmp = get_pte(mm->pgdir,addr,0);
//从pte获取page
struct Page *page = pte2page(*tmp);
//设置dirty_bit
SetDirtyBit(page);
}
/*
* _clock_init
*/
static int _clock_init(void) {
return 0;
}
/*
* _clock_set_unswappable
* 设置addr为不可被换出的
*/
static int _clock_set_unswappable(struct mm_struct *mm, uintptr_t addr) {
list_entry_t *head = (list_entry_t*) mm->sm_priv;
list_entry_t *iter = head->next;
//从虚拟地址获取pte
uintptr_t *tmp = get_pte(mm->pgdir,addr,0);
//从pte获取page
struct Page *page = pte2page(*tmp);
while(iter != head){
if(iter == &(page->pra_page_link)){
list_del(iter);
return 0;
}
iter = iter->next;
}
cprintf("Cannot find addr in list");
assert(0);
return 1;
}
static int _clock_tick_event(struct mm_struct *mm) {
return 0;
}测试函数
static int _clock_check_swap(struct mm_struct *mm) {
cprintf("write Virt Page c in clock_check_swap\n");
visit(mm,0x3000,0x0c);
cprintf("PGFAULT_NUM:%d\n",pgfault_num);
cprintf("write Virt Page a in clock_check_swap\n");
visit(mm,0x1000,0x0a);
//assert(pgfault_num == 4);
cprintf("PGFAULT_NUM:%d\n",pgfault_num);
cprintf("write Virt Page d in clock_check_swap\n");
visit(mm,0x4000, 0x0d);
//assert(pgfault_num == 4);
cprintf("PGFAULT_NUM:%d\n",pgfault_num);
cprintf("write Virt Page b in clock_check_swap\n");
visit(mm,0x2000 ,0x0b);
//assert(pgfault_num == 4);
cprintf("PGFAULT_NUM:%d\n",pgfault_num);
cprintf("write Virt Page e in clock_check_swap\n");
visit(mm,0x5000 , 0x0e);
cprintf("PGFAULT_NUM:%d\n\n",pgfault_num);
//assert(pgfault_num == 5);
cprintf("write Virt Page b in clock_check_swap\n");
visit(mm,0x2000, 0x0b);
//assert(pgfault_num == 5);
cprintf("PGFAULT_NUM:%d\n\n",pgfault_num);
cprintf("write Virt Page a in clock_check_swap\n");
visit(mm, 0x1000 , 0x0a);
cprintf("PGFAULT_NUM:%d\n\n",pgfault_num);
//assert(pgfault_num == 6);
cprintf("write Virt Page b in clock_check_swap\n");
visit(mm, 0x2000 , 0x0b);
cprintf("PGFAULT_NUM:%d\n\n",pgfault_num);
//assert(pgfault_num == 7);
cprintf("write Virt Page c in clock_check_swap\n");
visit(mm, 0x3000 , 0x0c);
//assert(pgfault_num == 8);
cprintf("PGFAULT_NUM:%d\n\n",pgfault_num);
cprintf("write Virt Page d in clock_check_swap\n");
visit(mm, 0x4000 , 0x0d);
cprintf("PGFAULT_NUM:%d\n\n",pgfault_num);
//assert(pgfault_num == 9);
return 0;
}其中由于每次访问时需要吧dirty bit置为1，而直接等号赋值不能实现该功能，故将访问打包到visit函数内
输出分析
-
前四次是冷启动，必然会出现四次miss
set up init env for check_swap begin!
page fault at 0x00001000: K/W [no page found].
page fault at 0x00002000: K/W [no page found].
page fault at 0x00003000: K/W [no page found].
page fault at 0x00004000: K/W [no page found].
set up init env for check_swap over! -
后面的输出分析见下表格
set up init env for check_swap over!
write Virt Page c in clock_check_swap
PGFAULT_NUM:4
write Virt Page a in clock_check_swap
PGFAULT_NUM:4
write Virt Page d in clock_check_swap
PGFAULT_NUM:4
write Virt Page b in clock_check_swap
PGFAULT_NUM:4
write Virt Page e in clock_check_swap
page fault at 0x00005000: K/W [no page found]. Let's find victim!!!
Not good
Not good
Not good
Not good
Hit head!
Find it!!! swap_out: i 0, store page in vaddr 0x1000 to disk swap entry 2
PGFAULT_NUM:5 write Virt Page b in clock_check_swap
PGFAULT_NUM:5 write Virt Page a in clock_check_swap
page fault at 0x00001000: K/W [no page found]. Let's find victim!!!
Not good
Find it!!! swap_out: i 0, store page in vaddr 0x3000 to disk swap entry 4
swap_in: load disk swap entry 2 with swap_page in vadr 0x1000
PGFAULT_NUM:6 write Virt Page b in clock_check_swap
PGFAULT_NUM:6 write Virt Page c in clock_check_swap
page fault at 0x00003000: K/W [no page found]. Let's find victim!!!
Find it!!! swap_out: i 0, store page in vaddr 0x4000 to disk swap entry 5
swap_in: load disk swap entry 4 with swap_page in vadr 0x3000
PGFAULT_NUM:7 write Virt Page d in clock_check_swap
page fault at 0x00004000: K/W [no page found]. Let's find victim!!!
Not good
Not good
Not good
Hit head!
Not good
Find it!!! swap_out: i 0, store page in vaddr 0x5000 to disk swap entry 6
swap_in: load disk swap entry 5 with swap_page in vadr 0x4000
PGFAULT_NUM:8 count is 0, total is 7
check_swap() succeeded!实际情况分析如图：
Lab8 内核错误 用户程序ls错误
利用Lab8练习2写好的程序，测试ls（ls也写错了，下面为修改过的ls）
查看内核代码，发现sfs_lookup()写错了，下面是修改过的sfs_lookup()
这里只是随手改的，没有管协定文件目录长度，最大设置为40
暴力遍历分解子目录
/*
* sfs_lookup - Parse path relative to the passed directory
* DIR, and hand back the inode for the file it
* refers to.
*/
static int
sfs_lookup(struct inode *node, char *path, struct inode **node_store) {
struct sfs_fs *sfs = fsop_info(vop_fs(node), sfs);
assert(*path != '\0' && *path != '/');
vop_ref_inc(node);
struct sfs_inode *sin = vop_info(node, sfs_inode);
if (sin->din->type != SFS_TYPE_DIR) {
vop_ref_dec(node);
return -E_NOTDIR;
}
struct inode *subnode;
struct sfs_inode *cur_node = sin;
// cprintf("Show Path:%s\n",path);
//开始拆分
char tmp[40];
int i = 0,j = 0,ret = 0;
for(j = 0;;j++){
//末尾
if(path[j]=='\0'){
tmp[i] = '\0';
i = 0;
// cprintf("Find: %s\n",tmp);
ret = sfs_lookup_once(sfs, cur_node, tmp, &subnode, NULL);
break;
}
//遇到/
if(path[j]=='/'){
tmp[i] = '\0';
i = 0;
// cprintf("Find: %s\n",tmp);
if((ret = sfs_lookup_once(sfs, cur_node, tmp, &subnode, NULL))!=0) break;
//cur_node为当前目录inode
cur_node = vop_info(subnode, sfs_inode);
}
//正常
else{
tmp[i]=path[j];
i++;
}
}
vop_ref_dec(node);
if (ret != 0) {
return ret;
}
*node_store = subnode;
return 0;
}修改ls里面的bug：
int lsdir(const char *path) {
struct stat __stat, *stat = &__stat;
int ret;
DIR *dirp = opendir(path);
if (dirp == NULL) {
return -1;
}
struct dirent *direntp;
char tmppath[40];
while ((direntp = readdir(dirp)) != NULL) {
strcpy(tmppath,path);
strcat(tmppath,"/");
strcat(tmppath,direntp->name);
// printf("File has %s\n",tmppath);
if ((ret = getstat(tmppath, stat)) != 0) {
goto failed;
}
lsstat(stat, direntp->name);
}
printf("lsdir: step 4\n");
closedir(dirp);
return 0;
failed:
closedir(dirp);
return ret;
}修改disk0的文件系统如图，测试ls正常：
