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#include #include #include #include #include #include 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_swapPGFAULT_NUM:4write Virt Page a in clock_check_swapPGFAULT_NUM:4write Virt Page d in clock_check_swapPGFAULT_NUM:4write Virt Page b in clock_check_swapPGFAULT_NUM:4write Virt Page e in clock_check_swappage fault at 0x00005000: K/W [no page found].Let's find victim!!!Not goodNot goodNot goodNot goodHit head!Find it!!!swap_out: i 0, store page in vaddr 0x1000 to disk swap entry 2PGFAULT_NUM:5write Virt Page b in clock_check_swapPGFAULT_NUM:5write Virt Page a in clock_check_swappage fault at 0x00001000: K/W [no page found].Let's find victim!!!Not goodFind it!!!swap_out: i 0, store page in vaddr 0x3000 to disk swap entry 4swap_in: load disk swap entry 2 with swap_page in vadr 0x1000PGFAULT_NUM:6write Virt Page b in clock_check_swapPGFAULT_NUM:6write Virt Page c in clock_check_swappage 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 5swap_in: load disk swap entry 4 with swap_page in vadr 0x3000PGFAULT_NUM:7write Virt Page d in clock_check_swappage fault at 0x00004000: K/W [no page found].Let's find victim!!!Not goodNot goodNot goodHit head!Not goodFind it!!!swap_out: i 0, store page in vaddr 0x5000 to disk swap entry 6swap_in: load disk swap entry 5 with swap_page in vadr 0x4000PGFAULT_NUM:8count is 0, total is 7check_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 intsfs_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正常：
